package bridge;

import java.io.*;
import java.util.*;
/*
 * Name : Bridge
 * Problem ID: 110403
 * Name: Kenny Chong
 * DateL 4/23/2012 3:38 PM 
 */
class Main implements Runnable 
{
	static String ReadLn(int maxLength) 
    {
        byte line[] = new byte[maxLength];
        int length = 0;
        int input = -1;
        try {
            while (length < maxLength) {
                input = System.in.read();
                if ((input < 0) || (input == '\n'))
                    break;
                line[length++] += input;
            }

            if ((input < 0) && (length == 0))
                return null;
            return new String(line, 0, length);
        } catch (IOException e) {
            return null;
        }
    }
	
	public static void main(String [] args)
	{
		new Main().run();
	}
	
	public void run()
	{
		new Bridge().run();
	}
}

class Bridge implements Runnable
{
	static int MAX_LENGTH = 1500;
	
	public void run()
	{
		// Read number of cases.
		int numOfCases = Integer.parseInt(Main.ReadLn(MAX_LENGTH).trim());
		
		// Read Blank line.
		Main.ReadLn(MAX_LENGTH);
		
		for (int i = 0; i < numOfCases; i++)
		{
			if (i != 0)
			{
				System.out.println();
				Main.ReadLn(MAX_LENGTH);
			}
			
			// Read the speeds of people.
			int speeds = Integer.parseInt(Main.ReadLn(MAX_LENGTH).trim());
			
			// Create data structure.
			ArrayList<Integer> start = new ArrayList<Integer>();
			
			for (int j = 0; j < speeds; j++)
			{
				int personSpeed = Integer.parseInt(Main.ReadLn(MAX_LENGTH).trim());
				
				start.add(personSpeed);
			}
			
			evalMinCrossTime(start);
		} while (Main.ReadLn(MAX_LENGTH) != null);
	}
	
	public void evalMinCrossTime(ArrayList<Integer> start)
	{
		// Create the end bridge.
		ArrayList<Integer> end = new ArrayList<Integer>();
		
		// Sort start bridge.
		Collections.sort(start);
		
		// Keep a record of people moving back and forth across the bridge.
		ArrayList<Integer> tracker = new ArrayList<Integer>();
		
		// Sentinel value (later used for printing).
		tracker.add(-1);
		
		int stratOneResult = 0;
		int stratTwoResult = 0;
		int total = 0;
		
		// Start the simulation until start bridge is empty.
		while (!start.isEmpty())
		{
			// Determine if start bridge has more than 3 people.
			if (start.size() > 3)
			{
				// Evaluate using strategy one.
				stratOneResult = calStrategyOne(start, end);
				
				// Evaluate using strategy Two.
				stratTwoResult = calStrategyTwo(start, end);
				
				if (stratOneResult < stratTwoResult)
				{
					total += stratOneResult;
					performStrategyOne(start, end, tracker);
				}
				else
				{
					total += stratTwoResult;
					performStrategyTwo(start, end, tracker);
				}
			}
			else
			{
				if (start.size() == 1)
				{
					total += start.get(0);
					tracker.add(start.get(0));
					start.remove(0);
				}
				else
				{
					total += performInitStrategy(start, end, tracker);
				}
			}
		}
		
		printResults(tracker, total);
	}

	public int performInitStrategy(ArrayList<Integer> start, ArrayList<Integer> end, ArrayList<Integer> tracker)
	{
		int crosserOne = 0;
		int crosserTwo = 0;
		int crosserReturn = 0;
		
		int record = 0;
		
		while (!start.isEmpty())
		{
			Collections.sort(start);
			
			// Retrieve the last few speeds starting with the front two at start bridge.
			crosserOne = start.get(0);
			crosserTwo = start.get(1);
			
			tracker.add(crosserOne);
			tracker.add(crosserTwo);
			
			record += crosserTwo;
			
			start.remove(0);
			start.remove(0);
			
			end.add(crosserOne);
			end.add(crosserTwo);
			
			Collections.sort(end);
	
			if (!start.isEmpty())
			{
				crosserReturn = end.get(0);
				
				tracker.add(crosserReturn);
				
				record += crosserReturn;
				
				start.add(crosserReturn);
			}
		}
		return record;
	}
	
	/*
	 * With sorted speeds (starting at start bridge), if we have speeds A B C D
	 * we will cross the two fastest speeds to end bridge, return the fastest
	 * speed to start bridge, take the slowest two across to end bridge, return
	 * the fastest speed at end bridge. (AB. A. CD, B).
	 */
	public int calStrategyOne(ArrayList<Integer> start, ArrayList<Integer> end)
	{
		// Create temporary start and end bridges.
		ArrayList<Integer> tempStart = new ArrayList<Integer>(start);
		ArrayList<Integer> tempEnd = new ArrayList<Integer>(end);
		
		// Copy values from original start and end to the temps.
		Collections.copy(tempStart, start);
		Collections.copy(tempEnd, end);
		
		int record = 0;
		
		// Evaluate crossing.
		// Take the fastest two speeds and cross them.
		if (!tempStart.isEmpty() && tempStart.size() >= 2)
		{
			// Cross two to end bridge.
			record += crossToEndBridge(0, 1, tempStart, tempEnd);
			
			// Cross one to start bridge.
			record += crossToStartBridge(tempStart, tempEnd);
			
			// Cross two to end bridge.
			record += crossToEndBridge(tempStart.size() - 1, tempStart.size() - 2, tempStart, tempEnd);
			
			// Finally record the fastest crosser of end (we will send him/her back to start).
			record += crossToStartBridge(tempStart, tempEnd);
		}
		
		return record;
	}
	
	public int crossToStartBridge(ArrayList<Integer> start, ArrayList<Integer> end)
	{
		int crosserReturn = 0;
		
		// Sort temp end bridge.
		Collections.sort(end);
		
		// Retrieve highest speed from end bridge and cross him back to start.
		crosserReturn = end.get(0);
		
		// Remove from end.
		end.remove(0);
		
		// Add him to start bridge.
		start.add(crosserReturn);
		
		Collections.sort(start);
		
		return crosserReturn;
	}
	
	public int crossToEndBridge(int personLocationOne, int personLocationTwo, ArrayList<Integer> start, ArrayList<Integer> end)
	{
		int crosserOne = 0;
		int crosserTwo = 0;
		
		crosserOne = start.get(personLocationOne);
		crosserTwo = start.get(personLocationTwo);
		
		// Remove them from start bridge.
		start.set(personLocationOne, -1);
		start.set(personLocationTwo, -1);
		
		Collections.sort(start);
		start.remove(0);
		start.remove(0);
		
		// Add them to the temp end bridge.
		end.add(crosserOne);
		end.add(crosserTwo);
		
		// Sort temp end bridge.
		Collections.sort(end);

		return (crosserOne > crosserTwo ? crosserOne : crosserTwo);
	}
	
	public void crossToStartBridge(ArrayList<Integer> start, ArrayList<Integer> end, ArrayList<Integer> tracker)
	{
		int crosserReturn = 0;
		
		// Sort temp end bridge.
		Collections.sort(end);
		
		// Retrieve highest speed from end bridge and cross him back to start.
		crosserReturn = end.get(0);
		
		tracker.add(crosserReturn);
		
		// Remove from end.
		end.remove(0);
		
		// Add him to start bridge.
		start.add(crosserReturn);
		
		Collections.sort(start);
	}
	
	public void crossToEndBridge(int personLocationOne, int personLocationTwo, ArrayList<Integer> start, ArrayList<Integer> end, ArrayList<Integer> tracker)
	{
		int crosserOne = 0;
		int crosserTwo = 0;
		
		crosserOne = start.get(personLocationOne);
		crosserTwo = start.get(personLocationTwo);
		
		tracker.add(crosserOne);
		tracker.add(crosserTwo);
		
		// Remove them from start bridge.
		start.set(personLocationOne, -1);
		start.set(personLocationTwo, -1);
		
		Collections.sort(start);
		start.remove(0);
		start.remove(0);
		
		// Add them to the temp end bridge.
		end.add(crosserOne);
		end.add(crosserTwo);
		
		// Sort temp end bridge.
		Collections.sort(end);
	}
	
	/*
	 * With sorted speeds (starting at start bridge), if we have speeds A B C D
	 * we will cross the fastest and slowest speeds to end bridge, return the fastest
	 * speed to start bridge, take the fastest and slowest speeds across to end bridge, return
	 * the fastest speed at end bridge. (AD. A. AC, A).
	 */
	public int calStrategyTwo(ArrayList<Integer> start, ArrayList<Integer> end)
	{
		// Create temporary start and end bridges.
		ArrayList<Integer> tempStart = new ArrayList<Integer>(start);
		ArrayList<Integer> tempEnd = new ArrayList<Integer>(end);
		
		// Copy values from original start and end to the temps.
		Collections.copy(tempStart, start);
		Collections.copy(tempEnd, end);
		
		int record = 0;
		
		// Evaluate crossing.
		// Take the fastest and slowest speeds and cross them.
		if (!tempStart.isEmpty() && tempStart.size() >= 2)
		{
			// Cross two to end bridge.
			record += crossToEndBridge(0, tempStart.size() - 1, tempStart, tempEnd);
			
			// Cross one to start bridge.
			record += crossToStartBridge(tempStart, tempEnd);
			
			// Cross two to end bridge.
			record += crossToEndBridge(0, tempStart.size() - 1, tempStart, tempEnd);
			
			// Finally record the fastest crosser of end (we will send him/her back to start).
			record += crossToStartBridge(tempStart, tempEnd);
		}
		
		return record;
	}
	
	public void performStrategyOne(ArrayList<Integer> start, ArrayList<Integer> end, ArrayList<Integer> tracker)
	{
		// Evaluate crossing.
		// Take the fastest two speeds and cross them.
		if (!start.isEmpty() && start.size() >= 2)
		{
			// Cross two to end bridge.
			crossToEndBridge(0, 1, start, end, tracker);
			
			// Cross one to start bridge.
			crossToStartBridge(start, end, tracker);
			
			// Cross two to end bridge.
			crossToEndBridge(start.size() - 2, start.size() - 1, start, end, tracker);
			
			// Finally record the fastest crosser of end (we will send him/her back to start).
			crossToStartBridge(start, end, tracker);
		}
	}
	
	public void performStrategyTwo(ArrayList<Integer> start, ArrayList<Integer> end, ArrayList<Integer> tracker)
	{
		// Evaluate crossing.
		// Take the fastest two speeds and cross them.
		if (!start.isEmpty() && start.size() >= 2)
		{
			// Cross two to end bridge.
			crossToEndBridge(0, start.size() - 1, start, end, tracker);
			
			// Cross one to start bridge.
			crossToStartBridge(start, end, tracker);
			
			// Cross two to end bridge.
			crossToEndBridge(0, start.size() - 1, start, end, tracker);
			
			// Finally record the fastest crosser of end (we will send him/her back to start).
			crossToStartBridge(start, end, tracker);
		}
	}
	
	public void printResults(ArrayList<Integer> tracker, int total)
	{		
		String x = "";
		System.out.println(total);
		
		if (tracker.size() == 2)
		{
			System.out.println(tracker.get(1));
		}
		else
		{
			for (int i = 1; i < tracker.size(); i++)
			{
				if (i % 3 == 0)
				{
					System.out.println(x.trim());
					System.out.println(tracker.get(i));
					x = "";
				}
				else
				{
					x += tracker.get(i) + " ";
				}
			}
			
			System.out.println(x.trim());
		}
	}
}
